package com.nine.algorithm.recursion.insertion;

/**
 * @author nine
 * @version 1.0
 * @description 插入排序
 * @date 24/4/30 23:19
 */
public class InsertionSort {

	public static void sort(int[] a) {
		insertion(a, 1);
	}

	/**
	 * 插入排序
	 * 在a数组中，第一个数，一定是排好序的，
	 *
	 * @param a   数组
	 * @param low 排序的左边界，一开始可以直接给1
	 */
	private static void insertion(int[] a, int low) {
		if (low == a.length) {
			return;
		}
		// 排好序的后面一个未排序的元素
		int t = a[low];
		// 排好序的最后一个元素
		int i = low - 1;
		// i会出现-1的情况，必须要i>=0
		while (i >= 0 && a[i] > t) {
			// 空出插入的位置
			a[i + 1] = a[i];
			i--;
		}

		// 如果位置不变的话，就没必要赋值了
		if (i + 1 != low) {
			// 找到插入的位置
			a[i + 1] = t;
		}

		insertion(a, low + 1);
	}

}
